/*
 * @lc app=leetcode.cn id=16 lang=cpp
 *
 * [16] 最接近的三数之和
 */

// @lc code=start
class Solution
{
public:
    int threeSumClosest(vector<int> &nums, int target)
    {
        //最接近的三数之和
        //方法也是双指针
        int len = INT32_MAX; //最短距离
        int res;
        //题目已经限制size>=3
        int first; //首指针
        sort(nums.begin(), nums.end());
        for (first = 0; first < nums.size() - 2; first++)
        {
            if (first > 0 && nums[first - 1] == nums[first])
            {
                continue;
            }
            int left = first + 1;
            int right = nums.size() - 1;
            while (left < right)
            {
                int sum = nums[first] + nums[left] + nums[right];

                if (sum > target)
                {
                    right--;
                    while (left < right && nums[right] == nums[right + 1])
                    {
                        right--;
                    }
                }
                else if (sum < target)
                {
                    left++;
                    while (left + 1 < right && nums[left] == nums[left - 1])
                    {
                        left++;
                    }
                }
                else
                {
                    return sum;
                }
                if (abs(target - sum) < len)
                {
                    len = abs(target - sum);
                    res = sum;
                }
            }
        }
        return res;
    }
};
// @lc code=end
